function TreeNode(x) {
	this.val = x;
	this.left = null;
	this.right = null;
}

function BST(list) {
	this.root = null;
	list && list.forEach((item) => {
		this.insert(item);
	});
}

// 插入节点
BST.prototype.insert = function(x) {
	let n = new TreeNode(x);
	if(!this.root) {
        this.root = n;
    }else {
        let result = [this.root];//入队
        while(result.length) {
            let cur = result.shift();//出队
            if(!cur.left) {
                cur.left = n;
                break;
            }else if(!cur.right) {
                cur.right = n;
                break;
            }else {
                result.push(cur.left);//入队
                result.push(cur.right);//入队
            }
        }
    }
};

// 层序遍历结果
BST.prototype.levelOrder = function() {
    if (!this.root) return [];
    let ret = [];

    let result = [this.root];//入队
    while(result.length) {
        let newResult = [];
        let arr = [];
        for(let i = 0; i < result.length; i++) {
            let item = result[i];
            arr.push(item.val);
            if(item.left) {
                newResult.push(item.left);
            }
            if(item.right) {
                newResult.push(item.right);
            }
        }
        result = newResult;
        ret.push(arr);
    }

    return ret;
};

// 判断是否是完全二叉树
BST.prototype.isCompleteTree = function() {
    function isCompleteTree (root) {
        if(!root) return true;
        if(!root.left && root.right) return false;
        return isCompleteTree(root.left) && isCompleteTree(root.right);
    }
    return isCompleteTree(this.root);
};